package lc;
import java.util.*;
import org.junit.*;
public class Ex47 {
    class Solution2 {
        public List<List<Integer>> permuteUnique(int[] nums) {
            len = nums.length;
            res = new ArrayList<>();
            //默认全部没有用过
            used = new boolean[len];
            Arrays.sort(nums);
            dfs(0, nums, new ArrayList<>());
            return res;
        }
        List<List<Integer>> res;
        int len;
        boolean[] used;
        /**
         * 
         * @param idx 表示当前添加了多少个元素到path中
         * @param used[i] 表示i这个位置的元素有没有放到path中
         */
        public void dfs(int idx, int[] nums, List<Integer> path) {

            if (idx == len) {
                res.add(new ArrayList<>(path));
                return;
            }

            for (int i = 0; i < len; i++) {
                if (used[i]) continue;
                //因为逻辑上必须选，所以user[i - 1] == false要么是选了回退的，要么是因为之前选了所以不再选的
                if (i > 0 && nums[i - 1] == nums[i] && !used[i - 1]) {
                    continue;
                }
                path.add(nums[i]);
                used[i] = true;//选取当前位置
                dfs(idx + 1, nums, path);
                used[i] = false;
                path.remove(path.size() - 1);
            }

        }
    }

    @Test
    public void test() {
        Solution s = new Solution();
        int[] nums = new int[]{1,1,2};
        System.out.println(s.permuteUnique(nums));
    }

    class Solution {
        List<List<Integer>> res;
        int[] nums;
        int n;
        public List<List<Integer>> permuteUnique(int[] nums) {
            res = new ArrayList<>();
            this.nums = nums;
            n = nums.length;
            Arrays.sort(nums);
            dfs(0, new boolean[n], new ArrayList<>());
            return res;
        }

        public void dfs(int idx, boolean[] flags, List<Integer> cur) {
            if (idx == n) {
                res.add(new ArrayList<>(cur));
                return;
            }
            for (int i = 0; i < n; i++) {
                if (flags[i]) {
                    continue;
                }
                if (i > 0 && nums[i] == nums[i - 1] && !flags[i - 1]) {
                    continue;
                }
                cur.add(nums[i]);
                flags[i] = true;
                dfs(idx + 1, flags, cur);
                cur.remove(cur.size() - 1);
                flags[i] = false;
            }
        }
    }
}
